﻿/**
 * Copyright (C) 2011 original author and authors
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace NGuice.Inject.Internal.Util
{
    /// <summary>
    /// 一个高性能的，可靠的不可变的Set实现，用户可以指定迭代顺序。此集合不允许null元素。
    /// 与只读集合不一样，只读集合只是一个分离的集合的视图，他仍然能够改变，此类的一个
    /// 实例包含他们的私有数据且永远不能改变。这个类是常数集合的方便的类，同时能够方便的
    /// 让你防御性的拷贝集合给你的调用者。
    /// <remarks>
    /// 和大部分集合一样，不可变的集合中的元素并不代表是不可变的。由于这个理由，为了避免混淆，
    /// 强烈建议你在此集合中仅仅放置不可变的集合
    /// </remarks>
    /// 此类对HashSet的性能有显著的提高，这是由于众所周知的不可变对象的哈希算法导致。当此类的
    /// 工厂方法创建了基于哈希的实例时，ImmutableSortedSet子类将执行二进制搜索。
    /// 注意：此类虽然不是sealed的，但在外部不要进行子类化，他不提供公共或保护的构造器。因此，
    /// 此集合类型的实例本身是不可变的
    /// </summary>
    public abstract class ImmutableSet<T> : ImmutableCollection<T>, ISet<T>
    {
        internal ImmutableSet() { }

        public static readonly ImmutableSet<T> EMPTY_IMMUTABLE_SET = new EmptyImmutableSet();

        /// <summary>
        /// 如果GetHashCode方法运行快速，则为true
        /// </summary>
        public virtual bool IsHashCodeFast
        {
            get
            {
                return false;
            }
        }

        public override bool Equals(object obj)
        {
            if (obj == this)
            {
                return true;
            }
            if (obj is ImmutableSet<T> && IsHashCodeFast && ((ImmutableSet<T>)obj).IsHashCodeFast && GetHashCode() != obj.GetHashCode())
            {
                return false;
            }
            return Collections2.SetEquals(this, obj);
        }

        public override int GetHashCode()
        {
            int hashCode = 0;
            foreach (T o in this)
            {
                hashCode += o.GetHashCode();
            }
            return hashCode;
        }

        public override string ToString()
        {
            if (IsEmpty)
            {
                return "[]";
            }
            IEnumerator<T> enumerator = GetEnumerator();
            StringBuilder result = new StringBuilder(Count * 16);
            enumerator.MoveNext();
            result.Append('[').Append(enumerator.Current.ToString());
            for (int i = 1; i < Count; i++)
            {
                enumerator.MoveNext();
                result.Append(", ").Append(enumerator.Current.ToString());
            }
            return result.Append(']').ToString();
        }

        public virtual void ExceptWith(IEnumerable<T> other)
        {
            throw new NotSupportedException();
        }

        public virtual void IntersectWith(IEnumerable<T> other)
        {
            throw new NotSupportedException();
        }

        public virtual bool IsProperSubsetOf(IEnumerable<T> other)
        {
            if (other is ImmutableSet<T>)
            {
                ImmutableSet<T> otherSet = (ImmutableSet<T>)other;
                if (this.Count == 0)
                    return otherSet.Count > 0;//空集为任意非空集的子集
                if (this.Count < otherSet.Count)
                {
                    return otherSet.ContainsAll(this);
                }
            }
            return false;
        }

        public virtual bool IsProperSupersetOf(IEnumerable<T> other)
        {
            if (other is ImmutableSet<T>)
            {
                ImmutableSet<T> otherSet = (ImmutableSet<T>)other;
                return otherSet.IsProperSubsetOf(this);
            }
            return false;
        }

        public virtual bool IsSubsetOf(IEnumerable<T> other)
        {
            if (other is ImmutableSet<T>)
            {
                ImmutableSet<T> otherSet = (ImmutableSet<T>)other;
                if (this.Count == 0)
                    return otherSet.Count >= 0;//空集为任意非空集的子集
                if (this.Count <= otherSet.Count)
                {
                    return otherSet.ContainsAll(this);
                }
            }
            return false;
        }

        public virtual bool IsSupersetOf(IEnumerable<T> other)
        {
            if (other is ImmutableSet<T>)
            {
                ImmutableSet<T> otherSet = (ImmutableSet<T>)other;
                return otherSet.IsSubsetOf(this);
            }
            return false;
        }

        public virtual bool Overlaps(IEnumerable<T> other)
        {
            throw new NotImplementedException();
        }

        public virtual bool SetEquals(IEnumerable<T> other)
        {
            return Equals(other);
        }

        public virtual void SymmetricExceptWith(IEnumerable<T> other)
        {
            throw new NotSupportedException();
        }

        public virtual void UnionWith(IEnumerable<T> other)
        {
            throw new NotSupportedException();
        }

        /// <summary>
        /// 获取一个空的不可变集
        /// </summary>
        public static ImmutableSet<T> Of()
        {
            return ImmutableSet<T>.EMPTY_IMMUTABLE_SET;
        }

        /// <summary>
        /// 获取只包含一个元素的不可变集合，他不接受null值
        /// </summary>
        public static ImmutableSet<T> Of(T element)
        {
            return new SingletonImmutableSet<T>(element, element.GetHashCode());
        }

        /// <summary>
        /// 返回包含指定元素的不可变集合
        /// </summary>
        /// <exception cref="NullReferenceException">如果元素中有null</exception>
        public static ImmutableSet<T> Of(params T[] elements)
        {
            switch (elements.Length)
            {
                case 0:
                    return Of();
                case 1:
                    return Of(elements[0]);
                default:
                    return Create<T, T>(elements.ToList(), elements.Length);
            }
        }

        public static ImmutableSet<T> CopyOf<T, X>(IEnumerable<X> elements)
            where X : T
        {
            if (elements is ImmutableSet<T>)
            {
                ImmutableSet<T> set = (ImmutableSet<T>)elements;
                return set;
            }
            return CopyOfInternal<T, X>(elements.ToList());
        }

        public static ImmutableSet<T> CopyOf<T, X>(IEnumerator<X> elements)
           where X : T
        {
            return CopyOfInternal<T, X>(Lists.NewArrayList<X>(elements));
        }

        /// <summary>
        /// 返回一个可以连续构建不可变集合的构建器。他可以像StringBuilder一样以链表方式构建不可变集合。
        /// 构建完毕后，最后调用Build方法将最终输出不可变集合
        /// </summary>
        /// <example>
        /// ImmutableSet<Color> GOOGLE_COLORS = new ImmutableSet.Builder<Color>()
        ///                                                                      .AddAll(WEBSAFE_COLORS)
        ///                                                                      .Add(new Color(0, 191, 255))
        ///                                                                      .Build();}
        /// </example>
        public static Builder<T> GetBuilder()
        {
           return new Builder<T>();
        }

        private static ImmutableSet<T> CopyOfInternal<T, X>(ICollection<X> collection)
            where X : T
        {
            // TODO: Support concurrent collections that change while this method is running.
            switch (collection.Count)
            {
                case 0:
                    return ImmutableSet<T>.Of();
                case 1:
                    // TODO: Remove "ImmutableSet.<E>" when eclipse bug is fixed.
                    IEnumerator<X> e = collection.GetEnumerator();
                    e.MoveNext();
                    return ImmutableSet<T>.Of(e.Current);
                default:
                    return Create<T, X>(collection, collection.Count);
            }
        }

        private static ImmutableSet<T> Create<T, X>(IEnumerable<X> enumerable, int count) where X : T
        {
            // count is always the (nonzero) number of elements in the iterable
            int tableSize = Hashing.ChooseTableSize(count);
            object[] table = new object[tableSize];
            int mask = tableSize - 1;
            List<T> elements = new List<T>(count);
            int hashCode = 0;
            foreach (X element in enumerable)
            {
                int hash = element.GetHashCode();
                for (int i = Hashing.Smear(hash); true; i++)
                {
                    int index = i & mask;
                    object value = table[index];
                    if (value == null)
                    {
                        // Came to an empty bucket. Put the element here.
                        table[index] = element;
                        elements.Add(element);
                        hashCode += hash;
                        break;
                    }
                    else if (value.Equals(element))
                    {
                        break; // Found a duplicate. Nothing to do.
                    }
                }
            }
            // The iterable might have contained only duplicates of the same element.
            if (elements.Count == 1)
                return new SingletonImmutableSet<T>(elements[0], hashCode);
            else
                return new RegularImmutableSet<T>(elements.ToArray(), hashCode, table, mask);
        }

        ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        // inner class
        ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        private sealed class EmptyImmutableSet : ImmutableSet<T>
        {
            public override int Count
            {
                get
                {
                    return 0;
                }
            }

            public override bool IsEmpty
            {
                get
                {
                    return true;
                }
            }

            public override bool Contains(T obj)
            {
                return false;
            }

            private static readonly EmptyEnumerator<T> EMPTY_ENUMERATOR = new EmptyEnumerator<T>();

            private static readonly T[] EMPTY_ARRAY = new T[0];

            public override T[] ToArray()
            {
                return EMPTY_ARRAY;
            }


            public override bool Equals(object obj)
            {
                if (obj is ISet<T>)
                {
                    ISet<T> that = (ISet<T>)obj;
                    return that.Count == 0;
                }
                return false;
            }

            public override int GetHashCode()
            {
                return 0;
            }

            public override bool IsHashCodeFast
            {
                get
                {
                    return true;
                }
            }

            public override string ToString()
            {
                return "[]";
            }

            public override IEnumerator<T> GetEnumerator()
            {
                return EMPTY_ENUMERATOR;
            }
        }

        private sealed class SingletonImmutableSet<E> : ImmutableSet<E>
        {

            internal readonly E element;

            internal int hashCode;

            internal SingletonImmutableSet(E element, int hashCode)
            {
                this.element = element;
                this.hashCode = hashCode;
            }

            public override int Count
            {
                get
                {
                    return 1;
                }
            }

            public override bool IsEmpty
            {
                get
                {
                    return false;
                }
            }

            public override bool Contains(E obj)
            {
                return element.Equals(obj);
            }

            public override E[] ToArray()
            {
                return new E[] { element };
            }

            public override bool Equals(object obj)
            {
                if (obj == this)
                {
                    return true;
                }
                if (obj is SingletonImmutableSet<E>)
                {
                    SingletonImmutableSet<E> that = (SingletonImmutableSet<E>)obj;
                    return that.Count == 1 && element.Equals(that.element);
                }
                return false;
            }

            public override int GetHashCode()
            {
                return hashCode;
            }

            public override bool IsHashCodeFast
            {
                get
                {
                    return true;
                }
            }

            public override string ToString()
            {
                string elementToString = element.ToString();
                return new StringBuilder(elementToString.Length + 2)
                    .Append('[')
                    .Append(elementToString)
                    .Append(']')
                    .ToString();
            }

            public override IEnumerator<E> GetEnumerator()
            {
                return Enumerators.SingletonIterator<E>(element);
            }
        }

        internal class ArrayImmutableSet<E> : ImmutableSet<E>
        {

            private readonly E[] elements;

            internal ArrayImmutableSet(E[] elements)
            {
                this.elements = elements;
            }

            public override int Count
            {
                get
                {
                    return elements.Length;
                }
            }

            public override bool IsEmpty
            {
                get
                {
                    return false;
                }
            }

            public override IEnumerator<E> GetEnumerator()
            {
                return elements.AsEnumerable().GetEnumerator();
            }

            public override E[] ToArray()
            {
                E[] array = new E[Count];
                Array.Copy(elements, array, Count);
                return array;
            }

            public bool ContainsAll(ICollection<E> targets)
            {
                if (targets == this)
                {
                    return true;
                }
                if (!(targets is ArrayImmutableSet<E>))
                {
                    return elements.ContainsAll(targets);
                }
                if (targets.Count > Count)
                {
                    return false;
                }
                foreach (E target in ((ArrayImmutableSet<E>)targets).elements)
                {
                    if (!this.Contains(target))
                    {
                        return false;
                    }
                }
                return true;
            }
        }

        private sealed class RegularImmutableSet<E> : ArrayImmutableSet<E>
        {
            readonly object[] table; // the same elements in hashed positions (plus nulls)
            readonly int mask; // 'and' with an int to get a valid table index
            readonly int hashCode;

            internal RegularImmutableSet(E[] elements, int hashCode, object[] table, int mask)
                : base(elements)
            {
                this.table = table;
                this.mask = mask;
                this.hashCode = hashCode;
            }

            public override bool Contains(E target)
            {
                if (target == null)
                {
                    return false;
                }
                for (int i = Hashing.Smear(target.GetHashCode()); true; i++)
                {
                    object candidate = table[i & mask];
                    if (candidate == null)
                    {
                        return false;
                    }
                    if (candidate.Equals(target))
                    {
                        return true;
                    }
                }
            }

            public override int GetHashCode()
            {
                return hashCode;
            }

            public override bool IsHashCodeFast
            {
                get
                {
                    return true;
                }
            }
        }

        /** such as ImmutableMap.keySet() */
        internal abstract class TransformedImmutableSet<D, E> : ImmutableSet<E>
        {

            readonly D[] source;

            readonly int hashCode;

            internal TransformedImmutableSet(D[] source, int hashCode)
            {
                this.source = source;
                this.hashCode = hashCode;
            }

            internal abstract E Transform(D element);

            public override int Count
            {
                get
                {
                    return source.Length;
                }
            }

            public override bool IsEmpty
            {
                get
                {
                    return false;
                }
            }

            public override IEnumerator<E> GetEnumerator()
            {
                E[] e = ToArray();
                return e.AsEnumerable().GetEnumerator();
            }

            public override E[] ToArray()
            {
                E[] array = new E[Count];
                for (int i = 0; i < source.Length; i++)
                {
                    array[i] = Transform(source[i]);
                }
                return array;
            }

            public override int GetHashCode()
            {
                return hashCode;
            }

            public override bool IsHashCodeFast
            {
                get
                {
                    return true;
                }
            }
        }

        /// <summary>
        /// 一个创建不可变集合实例的构建器，他可以像StringBuilder一样以链表方式构建不可变集合。
        /// 构建完毕后，最后调用Build方法将最终输出不可变集合
        /// </summary>
        /// <example>
        /// ImmutableSet<Color> GOOGLE_COLORS = new ImmutableSet.Builder<Color>()
        ///         .AddAll(WEBSAFE_COLORS)
        ///         .Add(new Color(0, 191, 255))
        ///         .Build();}
        /// </example>
        public class Builder<T>
        {
            readonly List<T> contents = Lists.NewArrayList<T>();

            public Builder() { }

            public Builder<T> Add(T element)
            {
                Preconditions.CheckNotNull(element, "element cannot be null");
                contents.Add(element);
                return this;
            }

            public Builder<T> Add(params T[] elements)
            {
                Preconditions.CheckNotNull(elements, "elements cannot be null");
                List<T> elemsAsList = elements.ToList();
                Preconditions.CheckContentsNotNull(elemsAsList, "elements cannot contain null");
                contents.AddRange(elemsAsList);
                return this;
            }

            public Builder<T> AddAll<X>(IEnumerable<X> elements) where X : T
            {
                foreach (T elem in elements)
                {
                    Preconditions.CheckNotNull(elem, "elements contains a null");
                    contents.Add(elem);
                }
                return this;
            }

            public Builder<T> AddAll<X>(IEnumerator<X> elements) where X : T
            {
                while (elements.MoveNext())
                {
                    T element = elements.Current;
                    Preconditions.CheckNotNull(element, "element cannot be null");
                    contents.Add(element);
                }
                return this;
            }

            public ImmutableSet<T> Build()
            {
                return CopyOf<T, T>(contents);
            }
        }

        public new bool Add(T item)
        {
            throw new NotSupportedException();
        }

        //public new System.Collections.IEnumerator GetEnumerator()
        //{
        //    throw new NotImplementedException();
        //}

        //public abstract int Count
        //{
        //    get;
        //}

        //public abstract IEnumerator<T> GetEnumerator();

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }
    }
}
